package org.example.myleet.p952;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    private static final int[] PRIMES = new int[]{2, 3, 5, 7};

    public int largestComponentSize(int[] nums) {
        UnionFindSet ufSet = new UnionFindSet(nums);
        //保存具有相同质因数的nums的下标集合
        Map<Integer, List<Integer>> factorMapNumberIds = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int cur = nums[i];
            //质因数分解
            for (int j = 2; j * j <= cur; ++j) {
                if (cur % j == 0) {
                    //找到一个质因数
                    add(factorMapNumberIds, j, i);
                }
                while (cur % j == 0) {
                    //nums[i]中j这种质因数去除掉，之后再继续寻找下一个质因数
                    cur /= j;
                }
            }
            if (cur > 1) {
                //剩余的cur如果大于1，也算做一个质因数
                add(factorMapNumberIds, cur, i);
            }
        }
        for (Map.Entry<Integer, List<Integer>> entry : factorMapNumberIds.entrySet()) {
            //遍历所有的entry，将具有相同质因数的数字（有边相连）联合在一起
            List<Integer> numbers = entry.getValue();
            int root = ufSet.query(nums[numbers.get(0)]);
            for (Integer number : numbers) {
                ufSet.union(nums[number], root);
            }
        }
        //计算每一块的大小
        int maxComponentSize = 0;
        Map<Integer, Integer> componentSizeMap = new HashMap<>(nums.length);
        for (int num : nums) {
            int root = ufSet.query(num);
            int componentSize = componentSizeMap.getOrDefault(root, 0) + 1;
            componentSizeMap.put(root, componentSize);
            maxComponentSize = Math.max(maxComponentSize, componentSize);
        }
        return maxComponentSize;
    }

    private void add(Map<Integer, List<Integer>> factorMapNumbers, int j, int nums) {
        List<Integer> numbers = factorMapNumbers.getOrDefault(j, new ArrayList<>());
        numbers.add(nums);
        factorMapNumbers.put(j, numbers);
    }

    private boolean haveCofactor(int num1, int num2) {
        if (num1 == 1 || num2 == 1) {
            return false;
        }
        int c;
        while ((c = num1 % num2) != 0) {
            num1 = num2;
            num2 = c;
        }
        return num2 != 1;
    }

    static class UnionFindSet {
        Map<Integer, Integer> nodeParent;

        public UnionFindSet(int[] numbers) {
            nodeParent = new HashMap<>(numbers.length);
            for (int number : numbers) {
                nodeParent.put(number, number);
            }
        }

        public int query(int node) {
            int parent = nodeParent.get(node);
            if (node == parent) {
                return parent;
            }
            parent = query(parent);
            nodeParent.put(node, parent);
            return parent;
        }

        public void union(int x, int y) {
            int parentX = query(x);
            int parentY = query(y);
            nodeParent.put(parentX, parentY);
        }
    }
}
